package com.jzoffer;

public class BSTPostOrderArrays {
    public static void main(String[] args) {
        int []sequence = {1,2,5,4,3};
        System.out.println(verifySquenceOfBST(sequence));
        System.out.println(verifySquenceOfBST2(sequence));

    }

    // 非递归也是一个基于递归的思想：
    // 左子树一定比右子树小，因此去掉根后，数字分为left，right两部分，
    // right部分的最后一个数字是右子树的根，它比左子树所有值大，
    // 因此我们可以每次只看有子树是否符合条件即可。即使到达了左子树，
    // 左子树也可以看出由左右子树组成的树还像右子树那样处理。对于右子树，
    // 左子树的所有值都比右子树的根小可以暂时把他看出右子树的左子树，
    // 只需看看右子树的右子树是否符合要求即可
    public static boolean verifySquenceOfBST(int [] sequence){
        if(sequence == null || sequence.length < 1){
            return false;
        }
        int length = sequence.length - 1;
        if(length == -1){
            return false;
        }
        int i = 0;
        while (length > 0){
            // 左子树
            while (sequence[i] < sequence[length]){
                i++;
            }
            while (sequence[i] > sequence[length]){
                i++;
            }
            if(i < length){
                return false;
            }
            i = 0;
            length--;
        }
        return true;
    }

    public static boolean verifySquenceOfBST2(int [] sequence){
        if(sequence == null || sequence.length < 1){
            return false;
        }
        return subverifySquenceOfBST2(sequence,0,sequence.length-1);
    }

    private static boolean subverifySquenceOfBST2(int [] sequence,int start,int end){
        if(start >= end){
            return true;
        }
        int i = start;
        for(;i < end;i++){
            if(sequence[i] > sequence[end]){
                break;
            }
        }
        for(int j = i;j < end;j++){
            if(sequence[j] < sequence[end]){
                return false;
            }
        }
        return subverifySquenceOfBST2(sequence,start,i - 1) && subverifySquenceOfBST2(sequence,i,end - 1);
    }


}
